Exemplary embodiments of the invention relate to the art of computer system and, more particularly, to synchronizing resources in a computer system.
Current computer systems run a plurality of processes/threads in series and in parallel. Each process/thread vies independently, or in conjunction with associated processes and/or threads, for various shared computer resources. Shared computing resources can be either hardware resources or software resources. Examples of hardware resources are Input/Output systems, memory systems, processing systems, networking systems and the like. Examples of Input/Output systems include keyboard, mouse, and automatic data input/output devices such as, sensors and file read/write systems, USB drives and the like. Examples of memory systems include hard-drives, random access memory (RAM), read only memory (ROM) and/or variations such as, Persistent RAM (PSRAM), Dynamic RAM (DRAM), Static RAM (SRAM), as well as auxiliary memory systems such as, floppy drive, CD-RAM, DVD-RAM, Flash Memory and the like. Examples of processing systems include a Central Processing Unit (CPU) having one or multiple cores, graphics cards, auxiliary processing units such as, floating point accelerators, field programmable gate arrays (FPGA) or ASIC-s, and the like. Examples of network systems include sockets, USB ports, and Ethernet ports. Examples of software resources include virtual memory systems, network monitor programs, network daemons and various other Operating systems and monitoring programs and the like.
Resource synchronization concerns sharing resources between a plurality of process or threads such as shown in FIG. 1. When ready, a process/thread 101 generates a request 102 for a needed resource 103. The request for any particular type of resource depends on the type of computing the requesting process/thread is engaged in at the instant of generating the request. For example, an input request may be generated when the process/thread is expecting a data from an input device, and a memory request may be generated when the device is expected to “fetch” some data from the memory. If available, the resource is locked for access using a lock mechanism 104. Examples of lock mechanisms includes semaphore, mutex and the like. At this point process 101 utilizes the resource as needed. When no longer required, process 101 unlocks 105 resource 103 and exits. At this point, resource 103 is made available for other processes/threads such as indicated at 110. If resource 103 is not available when requested, process 110 joins a queue 115 until process 103 is available.
Items waiting in queue 115 are picked up using methods and algorithms such as Last In First Out (LIFO), First In First Out (FIFO), Least Recently Used (LRU) etc. or based on the priority assigned to the jobs being run by these processes or threads. While in queue 115 for resource 103, process/thread 110 is idle and valuable computations time is wasted. Effectively sharing resources with minimum down time or latency time is an active area of research in the Synchronization of Resources. However, process and threads still spend a lot of time waiting in the queue. Time in the queue could otherwise have been used for computation purposes.
Another serious consequence of making a process wait in a queue is the so-called “DeadLock”. Deadlock occurs when a set of blocked processes each holding a resource is waiting to acquire a resource held by another process in the set such as shown in FIG. 2 which illustrates four processes P, P2, P3 and P4 and two resources R1 and R2. Process P1 is waiting in a queue for Resource R2 and also making a request for Resource R1. Process P3 is waiting in a queue for Resource R1 and also making a request for Resource R2. Given that P1 can not come out of R2 unless R1 is available, and P3 can not get out of R1 until R2 becomes available, the system gets into an infinite idle state thereby creating a deadlock.